Masala #1047

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 30 %

#Matematika

3.3 (Baholar 7)

Muallif: Davlatbek Mirakilov

Is it Fibonacci?

Barchasi juda oddiy. Uchta butun $x,y,a$ sonlari beriladi.

$f(n) = \begin{cases} x & n = 0 \\ y & n = 1 \\ f(n-1)+f(n-2) & n \ge 2 \end{cases}$

bo`lsa, $f(a)$ ni $10^9+7$ ga bo`lgandagi qoldig`ini hisoblang.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - $T(1 \leq T \leq 2*10^5)$ testlar soni kiritiladi.

Har keyingi yangi qatorda, yangi test uchun - $x,y(0 \leq x,y \leq 10^9)$ va $a(0 \leq a \leq 2*10^5)$ sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda bittadan butun son, masala javobini chiqaring.

Misollar

#	input.txt	output.txt
1	11 3 5 2 1 1 6 6 7 1 1 1 12 7 4 5 5 6 9 3 2 0 1 1 40 2 2 19 19 75 6 976 85 12	8 13 7 233 41 309 3 165580141 13530 695 99104

Izoh:

Python tili uchun PyPy kompilyatoridan foydalanishni maslahat beramiz!

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin